/*
 * BackwardOracleMatching.cpp
 *
 *  Created on: 02-09-2013
 *      Author: Krzychu
 */

#include "BackwardOracleMatching.h"

#include "Config.h"
#include "List.h"

#define FALSE 0
#define TRUE 1
#define UNDEFINED -1

BackwardOracleMatching::BackwardOracleMatching()
{

}

BackwardOracleMatching::~BackwardOracleMatching()
{

}

std::string BackwardOracleMatching::getName()
{
	return "Backward Oracle Matching";
}

int getTransition(std::string pattern, int p, List** L, char c)
{
	int result = L[0]->getUndefined();

	List* cell = new List();

	if (p > 0 && pattern[p - 1] == c)
	{
		result = p - 1;
	}
	else
	{
		cell = L[p];
		while (cell->element != L[p]->getUndefined())
		{
			if (pattern[cell->element] == c)
			{
				return (cell->element);
			}
			else
			{
				cell = cell->next;
			}
		}
	}

	return result;
}

void setTransition(int p, int q, List** L)
{
	List* cell = new List();

	cell->element = q;
	cell->next = L[p];
	L[p] = cell;
}

void oracle(std::string pattern, char* T, List** L)
{
	int patternSize = pattern.size();

	int i, p, q;
	int S[patternSize + 1];
	char c;

	S[patternSize] = patternSize + 1;
	for (i = patternSize; i > 0; --i)
	{
		c = pattern[i - 1];
		p = S[i];
		while (p <= patternSize && (q = getTransition(pattern, p, L, c)) == UNDEFINED)
		{
			setTransition(p, i - 1, L);
			p = S[p];
		}
		S[i - 1] = (p == patternSize + 1 ? patternSize : q);
	}
	p = 0;
	while (p <= patternSize)
	{
		T[p] = TRUE;
		p = S[p];
	}
}

searchResult BackwardOracleMatching::execute(std::string text,
		std::string pattern)
{
	searchResult result;
	result.iterationsTaken = 0;

	int textSize = text.size();
	int patternSize = pattern.size();

	char* T = new char[patternSize + 1];
	List** L = new List*[patternSize + 1];
	for (int i = 0; i < patternSize; i++)
	{
		L[i] = new List();
	}

	int i, j, p, period, q, shift;

	/* Preprocessing */
	oracle(pattern, T, L);

	/* Searching */
	j = 0;
	while (j <= textSize - patternSize)
	{
		i = patternSize - 1;
		p = patternSize;
		shift = patternSize;
		while (i + j >= 0 && (q = getTransition(pattern, p, L, text[i + j])) != UNDEFINED)
		{
			p = q;
			if (T[p] == TRUE)
			{
				period = shift;
				shift = i;
			}
			--i;
		}
		if (i < 0)
		{
			result.positionsFound.push_back(j);
			if (Config::getInstance()->getFindOneOccurence())
			{
				return result;
			}

			shift = period;
		}
		j += shift;
	}

	return result;
}
